/*
 * @Author: your name
 * @Date: 2024-05-10 21:43:27
 * @LastEditTime: 2024-05-11 00:34:10
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\93.复原-ip-地址.cpp
 */
/*
 * @lc app=leetcode.cn id=93 lang=cpp
 *
 * [93] 复原 IP 地址
 */

// @lc code=start
class Solution {
public:
    vector<string> res;
    vector<string> path;
    bool isValid(string& s, int start, int end){
        if(end - start >= 1 && s[start] == '0'){
            // 长度大于1并且第一个是0
            return false;
        }
        if(end - start > 4){
            return false;
        }
        int val = 0;
        int count = 1;
        int bit;
        while(end >= start){
            bit = s[end] - '0';
            if(bit >=0 && bit <= 9){
                val += bit * count;
                count *= 10;
                end--;
            }else{
                return false;
            }


        }
        if(val > 255){
            return false;
        }
        return true;
    }
    void backtracking(string& s, int startIndex){
        if(path.size() == 4 && startIndex >= s.size()){
            // 分割到最后一个字符之后并且分割后的字段为4
            string str = "";
            for(auto p:path){
                str += p;
                str.push_back('.');
                
            }
            str.pop_back();
           res.push_back(str);
        }
        if(path.size() > 4){
            // 字段数大于4了，不符合
            return;
        }
        for(int i = startIndex; i < s.size(); i++){
            if(isValid(s,startIndex,i)){
                string tmp_str = s.substr(startIndex, i-startIndex+1);
                path.push_back(tmp_str);
            }else{
                continue;
            }
            backtracking(s, i+1);
            path.pop_back();
        }
    }
    vector<string> restoreIpAddresses(string s) {
        backtracking(s, 0);
        return res;
    }

};
// @lc code=end

